ARC068F Solitaire <计数DP>

Problem

Solitaire

Statement

Snuke has decided to play with cards and a deque (that is, a double-ended queue). Each card shows an integer from through , and the deque is initially empty.
Snuke will insert the cards at the beginning or the end of the deque one at a time, in order from to . Then, he will perform the following action times: take out the card from the beginning or the end of the deque and eat it.
Afterwards, we will construct an integer sequence by arranging the integers written on the eaten cards, in the order they are eaten. Among the sequences that can be obtained in this way, find the number of the sequences such that the element is . Print the answer modulo .

Constraints

Input

The input is given from Standard Input in the following format:

Output

Print the answer modulo .

Sample

Input #1

2 1

Output #1

1

Explanation #1
There is one sequence satisfying the condition: . One possible way to obtain this sequence is the following:
Insert both cards, and , at the end of the deque.
Eat the card at the beginning of the deque twice.
Input #2

17 2

Output #2

262144

Input #3

2000 1000

Output #3

674286644

标签：计数DP

Translation

有一个双端队列，将顺序加入其中，加在队头或队尾任意。随后将所有数弹出，每次弹队头或队尾任意。求有多少种出队序列使得在第个。

Solution

考虑双端队列的形态，其一定是开头从大到小直到，再从小到大直到最后。这样当在第个出队时，第个数一定可以划分为两个递减子序列。用表示第个数，最小值较小的子序列的最小值为的序列种数。考虑能由哪些状态转移，若第个数取，则有种序列；若第个数比大，则一定由转移，于是有。前缀和优化即可做到。

对这个队列进行出队到时，一定是前面没有数或后面没有数，那么队列中剩下的一定是一个递增序列或递减序列。那么在出队后，一定是要么弹出剩下的最小的数，要么弹出剩下的最大的数。可以知道对于每种出队序列第个数的情况，第个数一定有种情况，于是答案为。总复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define P 1000000007
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, f[2][MAX_N+5];
int main() {
    read(n), read(m);
    for (int i = 1; i <= n+1; i++) f[0][i] = 1;
    for (int i = 1, c = 1; i < m; i++, c ^= 1) {
        memset(f[c], 0, sizeof f[c]);
        for (int j = 1; j <= n-i+1; j++) f[c][j] = f[c^1][j];
        for (int j = n; j; j--) f[c][j] = (f[c][j]+f[c][j+1])%P;
    }
    int ans = f[(m-1)&1][2];
    for (int i = 1; i <= n-m-1; i++)
        ans = (ans<<1)%P;
    return printf("%d\n", ans), 0;
}